package com.codingvip.tree;

import com.codingvip.tree.util.TreePrintUtil;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @Author Tony.Han
 * @Created at 2020/4/4 12:48 下午
 * Desc:
 */
public class BuildTree {

    public static void main(String[] args) {
//        int[] arr1 = {1, 2, 3, 4, 5};
//        int[] arr2 = Arrays.copyOf(arr1, 5);
//        int[] arr3 = Arrays.copyOf(arr1, 10);
//        for (int item : arr2) {
//            System.out.print(item + " ");
//        }
//        System.out.println();
//        for (int value : arr3) {
//            System.out.print(value + " ");
//        }
        int[] preOrder = new int[]{3, 9, 20, 15, 7};
        int[] inOrder =  new int[]{9, 3, 15, 20, 7};
        int[] testTarge = new int[1];
        System.arraycopy(preOrder, 1, testTarge, 0, 1);

        BuildTree buildTree = new BuildTree();
        TreeNode treeNode=buildTree.buildTree(preOrder, inOrder);
        System.out.println(treeNode.toString());
//        System.out.println(testTarge.toString());
    }

    HashMap<Integer, Integer> dic = new HashMap<>();
    int[] po;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        po = preorder;
        for(int i = 0; i < inorder.length; i++) {
            dic.put(inorder[i], i);
        }
        return recur(0, 0, inorder.length - 1);
    }
    TreeNode recur(int pre_root, int in_left, int in_right) {
        if(in_left > in_right) return null;
        TreeNode root = new TreeNode(po[pre_root]);
        int i = dic.get(po[pre_root]);
        root.left = recur(pre_root + 1, in_left, i - 1);
        root.right = recur(pre_root + i - in_left + 1, i + 1, in_right);
        return root;
    }

//    public TreeNode buildTree(int[] preOrder, int[] inOrder) {
//        if (preOrder == null || preOrder.length <= 0) {
//            return null;
//        }
//        TreeNode root = new TreeNode(preOrder[0]);
//
//        int[] leftSubInorder =null;
//        int[] leftSubPreOrder = null;
//
//        int[] rightSubInorder = null;
//        int[] rithgSubPreOrder = null;
//
//
//        int nodeNum = 0;
//        int rightnodeNum = 0;
//        boolean begLeft=true;
//        for (int j = 0; j < inOrder.length; j++) {
//            if (begLeft && inOrder[j] != preOrder[0]) {
//                nodeNum++;
//            } else if (inOrder[j] == preOrder[0]) {
//                //Copy Left
//                leftSubInorder = new int[nodeNum];
//                leftSubPreOrder = new int[nodeNum];
//                System.arraycopy(preOrder,1,leftSubPreOrder,0,nodeNum);
//                System.arraycopy(inOrder,0,leftSubInorder,0,nodeNum);
//                begLeft = false;
//                continue;
//            } else if (!begLeft) {
//                rightnodeNum++;
//            }
//        }
//        if (rightnodeNum > 0) {
//
//            rithgSubPreOrder = new int[rightnodeNum];
//            rightSubInorder = new int[rightnodeNum];
//            System.arraycopy(preOrder,nodeNum+1,rithgSubPreOrder,0,rightnodeNum);
//            System.arraycopy(inOrder,nodeNum+1,rightSubInorder,0,rightnodeNum);
//        }
//        buildSubTree(root, true, leftSubPreOrder, leftSubInorder);
//        buildSubTree(root, false, rithgSubPreOrder,rightSubInorder);
//        return root;
//    }
//    private void buildSubTree(TreeNode root, boolean isLeft, int[] preOrder, int[] inOrder) {
//        if (preOrder == null || preOrder.length <= 0) {
//            return;
//        }
//        TreeNode current = new TreeNode(preOrder[0]);
//        TreeNode next = null;
//        if (isLeft) {
//            root.left = current;
//            next = root.left;
//        } else {
//            root.right = current;
//            next = root.right;
//        }
//        if(preOrder.length == 1){
//            return;
//        }
//        int[] leftSubInorder =null;
//        int[] leftSubPreOrder = null;
//
//        int[] rightSubInorder = null;
//        int[] rithgSubPreOrder = null;
//        int nodeNum = 0;
//        int rightnodeNum = 0;
//        boolean begLeft=true;
//        for (int j = 0; j < inOrder.length; j++) {
//            if (begLeft && inOrder[j] != preOrder[0]) {
//                nodeNum++;
//            } else if (inOrder[j] == preOrder[0]) {
//                //Copy Left
//                leftSubInorder = new int[nodeNum];
//                leftSubPreOrder = new int[nodeNum];
//                System.arraycopy(preOrder,1,leftSubPreOrder,0,nodeNum);
//                System.arraycopy(inOrder,0,leftSubInorder,0,nodeNum);
//                begLeft = false;
//                continue;
//            } else if (!begLeft) {
//                rightnodeNum++;
//            }
//        }
//        if (rightnodeNum > 0) {
//
//            rithgSubPreOrder = new int[rightnodeNum];
//            rightSubInorder = new int[rightnodeNum];
//            System.arraycopy(preOrder,nodeNum+1,rithgSubPreOrder,0,rightnodeNum);
//            System.arraycopy(inOrder,nodeNum+1,rightSubInorder,0,rightnodeNum);
//        }
//
//        buildSubTree(next, true, leftSubPreOrder, leftSubInorder);
//        buildSubTree(next, false, rithgSubPreOrder,rightSubInorder);
//
//
//    }
}
